// https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/submissions/
// 有负数，注意和 长度最小的子数组.cpp 对比

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long> sum(n + 1);
        int ans = n + 1;
        for (int i = 0; i < n; ++i) {
            sum[i + 1] = sum[i] + nums[i];
        }
        deque<int> d;
        for (int i = 0; i < n + 1; ++i) {
            while (!d.empty() && (sum[i] - sum[d.front()] >= k)) {
                ans = min(ans, i - d.front());
                d.pop_front();
            }
            while (!d.empty() && sum[i] <= sum[d.back()]) {
                d.pop_back();
            }
            d.push_back(i);
        }
        return ans == n + 1 ? -1 : ans;
    }
};